package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 * <p>
 * 链接：https://leetcode-cn.com/problems/house-robber
 * <p>
 * [1,2,3,1] 4
 * <p>
 * [2,7,9,3,1] 12
 * @version 1.0
 * @date 2021/11/24 11:06
 * 打家劫舍 I
 */
public class rob1 {

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
        System.out.println(rob1(new int[]{2, 7, 9, 3, 1}));
    }

    // 动态规划状态定义：dp[i] 表示经过 第 i 家后，获得的最大金额，isRob 表示 第i家 是否被偷
    // 动态规划初始值： dp[0] = nums[0]，isRob = true
    // 动态规划转移方程：dp[i] 只与 dp[i-1] 和 dp[i-2] ，第 i-1家是否被偷 有关
    // 滚动数组
    static int rob(int[] nums) {
        // 一家没偷
        int dp = 0;
        // 偷了第一家
        int dp0 = nums[0];
        // 上一家是否被偷
        boolean isRobe = true;
        int maxAmount = Math.max(dp, dp0);
        for (int i = 1; i < nums.length; i++) {
            if (isRobe) {
                if (nums[i] + dp > dp0) {
                    maxAmount = nums[i] + dp;
                    isRobe = true;
                    dp = dp0;
                    dp0 = maxAmount;
                } else {
                    isRobe = false;
                    dp = dp0;
                }
            } else {
                maxAmount = nums[i] + dp0;
                dp0 = maxAmount;
                isRobe = true;
            }
        }
        return maxAmount;
    }

    // 上面的方法 还可以简化逻辑：
    // 设 dp, dp0 为连续的两家，那么 dp1 的值为 Math.max( dp + nums[1], dp0)，解释如下：
    // 如果 dp0被偷，那么 dp1 = Math.max( dp + nums[1], dp0)
    // 如果 dp0 没有被偷，那么 dp1 = dp0 + nums[1]，因为dp0 没有被偷，所以  dp0必然等于 dp，所以dp1 = dp + nums[1]
    // 所以 dp1 = Math.max( dp + nums[1], dp0)， dp == dp0, dp + nums[1] >= dp0
    // 所以 无论dp0 是否被偷 dp1 的结果都是 Math.max( dp + nums[1], dp0)
    static int rob1(int[] nums) {
        // 一家没偷
        int dp = 0;
        // 偷了第一家
        int dp0 = nums[0];
        int maxAmount = Math.max(dp, dp0);
        for (int i = 1; i < nums.length; i++) {
            maxAmount = Math.max(dp + nums[i], dp0);
            dp = dp0;
            dp0 = maxAmount;
        }
        return maxAmount;
    }
}
